package com.example.myletcodelearing.one

import com.example.myletcodelearing.kmp.KmpTest
import java.util.*
import kotlin.collections.ArrayList
import kotlin.math.max

/**
 * @author tgw
 * @date 2022/9/30
 * @describe
 */
fun main(array: Array<String>) {
    val ss = "abbabde"
    var length = Solution5().longestPalindrome(ss)
    var length2 = Solution5().longestPalindrome(ss)
    var length3 = Solution5().longestPalindrome2(ss)
//    var length4 = Solution5().longestPalindrome3(ss)
    var length5 = Solution5().longestPalindrome4(ss)
//    ss.reversed()
//    print("最长回文子串：$length")
//    print("最长回文子串：$length2")
//    print("最长回文子串：$length3")
//    print("最长回文子串：$length4")
    print("最长回文子串：$length5")


}

private class Solution5 {
    fun longestPalindrome(s: String): String {
        if (s.length <= 1) {
            return s
        }
        var middle = s.length / 2
        var l = 0
        var r = 0
        if (s.length % 2 != 1) {
            l = 1
        }
        var middleS = ""



        while (middle - l >= 0) {
            if (middle == 0 && s.length >= 2) {
                if (s[middle] == s[1]) {
                    var ss = s.substring(middle, 1 + 1)
                    if (ss.length > middleS.length) {
                        middleS = s.substring(middle, 1 + 1)
                    }
                    return middleS
                }
            }
            if (s[middle - l] == s[middle + r]) {
                var ss = s.substring(middle - l, middle + r + 1)
                if (ss.length > middleS.length) {
                    middleS = s.substring(middle - l, middle + r + 1)
                }
                l++
                r++
            } else {
                middle--
                r = 0
                l = 0
            }
        }

        middle = s.length / 2
        l = 0
        r = 0
        if (s.length % 2 != 1) {
            r = 1
        }
        while (middle + r < s.length) {
            if (middle == s.length - 1 && s.length >= 2) {
                if (s[middle] == s[s.length - 2]) {
                    var ss = s.substring(s.length - 2, s.length)
                    if (ss.length > middleS.length) {
                        middleS = s.substring(s.length - 2, s.length)
                    }
                    return middleS
                }
            }

            if (s[middle - l] == s[middle + r]) {
                var ss = s.substring(middle - l, middle + r)
                if (ss.length > middleS.length) {
                    middleS = s.substring(middle - l, middle + r)
                }
                r++
                l++
            } else {
                middle++
                r = 0
                l = 0
            }
        }
        return middleS
    }

    fun longestPalindrome2(s: String): String {
        if (s.length <= 1) {
            return s
        }
        var start = 0
        var end = 0
//        for (i in 0 until s.length){
//            for (j in i until s.length){
//               if (isLong(i,j,s)){
//                   if (j-i>=end - start) {
//                       start = i
//                       end = j
//                   }
//               }
//            }
//        }
        //优化一版不必要的循环，s.length - i > (end - start+1)
        var i = 0
        while (i < s.length && s.length - i > (end - start + 1)) {
            for (j in i until s.length) {
                if (isLong(i, j, s)) {
                    if (j - i > end - start) {
                        start = i
                        end = j
                    }
                }
            }
            i++
        }
        var long = s.substring(start, end + 1)
        return long
    }


    //两边相等往中间缩
    fun isLong(i: Int, j: Int, s: String): Boolean {
        var i = i
        var j = j
        while (i <= j) {
            if (s[i] != s[j]) {
                return false
            } else {
                i++
                j--
            }
        }
        return true
    }


    fun longestPalindrome3(s: String?): String? {//"abbabde"
        if (s == null || s.length < 1) {
            return ""
        }
        var start = 0
        var end = 0
        for (i in 0 until s.length) {
            val len1 = expandAroundCenter(s, i, i)
            val len2 = expandAroundCenter(s, i, i + 1)
            val len = Math.max(len1, len2)
            if (len > end - start) {
                start = i - (len - 1) / 2
                end = i + len / 2
            }
        }
        return s.substring(start, end + 1)
    }

    fun expandAroundCenter(s: String, left: Int, right: Int): Int {
        var left = left
        var right = right
        while (left >= 0 && right < s.length && s[left] == s[right]) {
            --left
            ++right
        }
        return right - left - 1
    }

    //中心扩散法
    fun longestPalindrome4(s: String?): String? {
        if (s == null || s.length == 0) {
            return ""
        }

        val strLen = s.length

        var start = 0
        var end = 0
        for (i in 0 until strLen) {
            var array = expandAroundCenter4(s, i)
            if (array[1] - array[0] > end - start) {
                start = array[0]
                end = array[1]
            }
        }
        return s.substring(start, end + 1)
    }

    // "abbabde","babad",ccc,"xaabacxcabaaxcabaax"
    fun expandAroundCenter4(s: String, i: Int): IntArray {
        var array: IntArray = IntArray(2)
        array[0] = i
        array[1] = i
        var left = i
        var right = i

        while (left >= 0 && right < s.length) {
            //首先尽量向右扩展找到相同的数据，
            if (left >= i && s[left] == s[right]) {
                array[0] = left
                array[1] = right
                right++
            } else {
                //发现了 不一样的数据的话 ，左边减一
                //这个只有一次减一，因为需要对称所以后续都是要 ，左边=右边，因为右边已经加过一次下标了，并且不相等，所以走这里
                if (left == i) {
                    left--
                }
                if (left >= 0 && s[left] == s[right]) {
                    array[0] = left
                    array[1] = right
                    left--
                    right++
                } else {
                    break
                }
            }
        }

        return array
    }


    //动态规划
    fun longestPalindrome5(s: String): String? {
        val len = s.length
        if (len < 2) {
            return s
        }
        var maxLen = 1
        var begin = 0
        // dp[i][j] 表示 s[i..j] 是否是回文串
        val dp = Array(len) {
            BooleanArray(
                len
            )
        }
        // 初始化：所有长度为 1 的子串都是回文串
        for (i in 0 until len) {
            dp[i][i] = true
        }
        val charArray = s.toCharArray()
        // 递推开始
        // 先枚举子串长度
        for (L in 2..len) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (i in 0 until len) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                val j = L + i - 1
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break
                }
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true
                    } else {
                        dp[i][j] = dp[i + 1][j - 1]
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1
                    begin = i
                }
            }
        }
        return s.substring(begin, begin + maxLen)
    }



}